package com.leetcode.partition1;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/8/7 10:13
 */
public class LC70爬楼梯 {

    public static int climbStairs(int n) {
//        return backtracking(n, 0);
        return memoization(n, 0, new int[n]);
    }

    public static void main(String[] args) {
        System.out.println(climbStairs(40));
    }

    private static int memoization(int n, int cur, int[] memo) {
        if (cur > n) return 0;
        if (cur == n) return 1;
        if (memo[cur] != 0) return memo[cur];
        memo[cur] = memoization(n, cur + 1, memo) + memoization(n, cur + 2, memo);
        return memo[cur];
    }

    private static int backtracking(int n, int cur) {
        if (cur > n) return 0;
        if (cur == n) return 1;
        int count = 0;
        count += backtracking(n, cur + 1);
        count += backtracking(n, cur + 2);
        return count;
    }

    private static int dynamicProgramming(int n) {
        int[] dp = new int[n + 1];
        dp[0] = dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            //i台阶的总数=(i-2)级台阶的总数+(i-1)级台阶的总数
            dp[i] = dp[i - 2] + dp[i - 1];
        }
        System.out.println(Arrays.toString(dp));
        return dp[n];
    }
}
